Corelab Seminar
2015-2016
Andreas Goebel
Modular Counting and Graph Homomorphisms
Abstract.
The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who
famously introduced a problem for which counting modulo~$7$ is easy where counting modulo~$2$, is intractable. A
characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is
the case for exact (non-modular) counting.
A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial
structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and
as weighted sums of graph homomorphisms. Modular counting provides a rich setting in which to study the structure of
homomorphism problems.
In this talk we will discuss the complexity of counting graph homomorphisms modulo 2. Faben and Jerrum
are the first to study the complexity of counting graph homomorphisms modulo~$2$. They
show that for a specific family of target graphs the problem of counting homomorphisms to a graph modulo~2 is
computationally easy and conjecture that for every other target graph the problem is computationally hard. They also
prove their conjecture when $H$ is a tree.
Our results build upon the work of Faben and Jerrum. We first give a dichotomy theorem for the class of cactus graphs,
which are connected graphs in which every edge belongs to at most one cycle. We also confirm the conjecture of Faben and
Jerrum for all graphs that contain no 4-cycles.